{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Deletions to Make String Balanced"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumDeletions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使字符串平衡的最少删除次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，它仅包含字符&nbsp;<code>'a'</code> 和&nbsp;<code>'b'</code>​​​​ 。</p>\n",
    "\n",
    "<p>你可以删除&nbsp;<code>s</code>&nbsp;中任意数目的字符，使得&nbsp;<code>s</code> <strong>平衡</strong>&nbsp;。当不存在下标对&nbsp;<code>(i,j)</code>&nbsp;满足&nbsp;<code>i &lt; j</code> ，且&nbsp;<code>s[i] = 'b'</code> 的同时&nbsp;<code>s[j]= 'a'</code> ，此时认为 <code>s</code> 是 <strong>平衡 </strong>的。</p>\n",
    "\n",
    "<p>请你返回使 <code>s</code>&nbsp;<strong>平衡</strong>&nbsp;的 <strong>最少</strong>&nbsp;删除次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"aababbab\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>你可以选择以下任意一种方案：\n",
    "下标从 0 开始，删除第 2 和第 6 个字符（\"aa<strong>b</strong>abb<strong>a</strong>b\" -&gt; \"aaabbb\"），\n",
    "下标从 0 开始，删除第 3 和第 6 个字符（\"aab<strong>a</strong>bb<strong>a</strong>b\" -&gt; \"aabbbb\"）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"bbaaaaabb\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>唯一的最优解是删除最前面两个字符。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;要么是&nbsp;<code>'a'</code> 要么是&nbsp;<code>'b'</code>​<strong>&nbsp;</strong>。​</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-deletions-to-make-string-balanced](https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-deletions-to-make-string-balanced](https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aababbab\"', '\"bbaaaaabb\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp1, dp2 = 0, 0\n",
    "        for x in s:\n",
    "            if x == 'a':\n",
    "                dp1 += 1\n",
    "            elif x == 'b':\n",
    "                dp2 = max(dp1, dp2) + 1\n",
    "        return n - max(dp1, dp2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def minimumDeletions(self, s: str) -> int:\n",
    "    def minimumDeletions(self, s):\n",
    "        # Implement your solution here\n",
    "        S = s.upper()\n",
    "        # total_a_cnt = sum(1 for i in S if i == 'A')\n",
    "        # n = len(S)\n",
    "\n",
    "        # def sub_func(start_index, a_cnt):\n",
    "        #     # print(start_index, a_cnt)\n",
    "        #     if a_cnt == 0 or a_cnt == n - start_index:\n",
    "        #         return 0\n",
    "        #     if S[start_index] == 'B':\n",
    "        #         first_a_index = S.find('A', start_index)\n",
    "        #         # delete prefix B (first_a_index 'B's)\n",
    "        #         delete_b = first_a_index-start_index + sub_func(first_a_index, a_cnt)\n",
    "        #         return min(delete_b, a_cnt)\n",
    "        #     else:\n",
    "        #         first_b_index = S.find('B', start_index)\n",
    "        #         # first_b_index must be >= 1\n",
    "        #         skip_a_cnt = first_b_index - start_index\n",
    "        #         return sub_func(first_b_index, a_cnt-skip_a_cnt)\n",
    "\n",
    "        # return sub_func(0, total_a_cnt)\n",
    "        ans = cur = sum(1 for i in S if i == 'A')\n",
    "        for i in S:\n",
    "            if i == 'A':\n",
    "                cur -= 1\n",
    "            else:\n",
    "                cur += 1\n",
    "            ans = min(ans, cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        leftb=0\n",
    "        righta=s.count('a')\n",
    "        output=righta\n",
    "        for c in s:\n",
    "            if c=='a':\n",
    "                righta-=1\n",
    "            else:\n",
    "                leftb+=1\n",
    "            output=min(output,leftb+righta)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        a_num = s.count('a')\n",
    "        \n",
    "        \n",
    "        ans = a_num\n",
    "        b_num = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == 'a':\n",
    "                b_num = b_num\n",
    "                a_num -= 1\n",
    "            elif s[i] == 'b':\n",
    "                b_num = b_num + 1\n",
    "            ans = min(ans, b_num + a_num)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        leftb=0\n",
    "        righta=s.count('a')\n",
    "        output=righta\n",
    "        for c in s:\n",
    "            if c=='a':\n",
    "                righta-=1\n",
    "            else:\n",
    "                leftb+=1\n",
    "            output=min(output,leftb+righta)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        leftb=0\n",
    "        righta=s.count('a')\n",
    "        output=righta\n",
    "        for c in s:\n",
    "            if c=='a':\n",
    "                righta-=1\n",
    "            else:\n",
    "                leftb+=1\n",
    "            output=min(output,leftb+righta)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumDeletions(self, s: str) -> int:\r\n",
    "        leftb, righta = 0, s.count('a')\r\n",
    "        res = righta\r\n",
    "        for i in range(len(s)):\r\n",
    "            if s[i] == 'a':\r\n",
    "                righta -= 1\r\n",
    "            else:\r\n",
    "                leftb += 1\r\n",
    "            res = min(res, leftb + righta)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        ans=delete=s.count('a')    \n",
    "        for c in s:\n",
    "            # 右移分割线，如果是a就减少删除次数\n",
    "            if c=='a':\n",
    "                delete -=1 \n",
    "            # 如果是b就增加删除次数\n",
    "            else:\n",
    "                delete +=1\n",
    "            if delete<ans:\n",
    "                ans=delete\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        cnt_a, cnt_b = 0, 0\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                cnt_a += 1\n",
    "            else:\n",
    "                cnt_b += 1\n",
    "        res = min(cnt_a, cnt_b)\n",
    "        cnt_b = 0\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                cnt_a -= 1\n",
    "            else:\n",
    "                cnt_b += 1\n",
    "            res = min(res, cnt_a + cnt_b)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        cnt_b = 0\n",
    "        f = 0\n",
    "        for c in s:\n",
    "            if c=='b':\n",
    "                cnt_b += 1 #此刻前面所有的‘b'的数量，因为要同时删除\n",
    "            else:\n",
    "                f = min(f+1, cnt_b) #后者表示此刻为a，保留a则需要同时删除前面所有的b，前者表示删除此刻的a，则前面的b不用管了，只需要比上一步多一步（f+1）即可。            \n",
    "        return f\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        ans = delete = s.count('a')\n",
    "        for c in s:\n",
    "            delete -= 1 if c == 'a' else -1\n",
    "            if delete < ans:  # 手动 min 会快很多\n",
    "                ans = delete\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        length=len(s)\n",
    "        ans=delete=s.count('a')\n",
    "        \n",
    "        for c in s:\n",
    "            if c=='a':\n",
    "                delete -=1 \n",
    "            else:\n",
    "                delete +=1\n",
    "            if delete<ans:\n",
    "                ans=delete\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        leftb,righta=0,s.count('a')\n",
    "        res = righta\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                righta -= 1\n",
    "            else:\n",
    "                leftb+=1\n",
    "            res = min(res, leftb+righta)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        leftb = 0\n",
    "        righta = s.count('a')\n",
    "        res = righta #假设最少需要删除所有的 “a”\\text{``a''}“a”\n",
    "        for c in s:\n",
    "            if c == 'b':\n",
    "                leftb += 1\n",
    "            else:\n",
    "                righta -= 1\n",
    "            # 枚举所有分割线\n",
    "            res = min(res,leftb+righta)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        leftb, righta = 0, s.count(\"a\")\n",
    "        cnt = righta\n",
    "        for ch in s:\n",
    "            if ch == \"a\":\n",
    "                righta -= 1\n",
    "            else:\n",
    "                leftb += 1\n",
    "            cnt = min(cnt, leftb + righta)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        leftb, righta = 0, s.count(\"a\")\n",
    "        cnt = righta\n",
    "        for ch in s:\n",
    "            if ch == \"a\":\n",
    "                righta -= 1\n",
    "            else:\n",
    "                leftb += 1\n",
    "            cnt = min(cnt, leftb + righta)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        leftb, righta = 0, s.count('a')\n",
    "        res = righta\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                righta -= 1\n",
    "            else:\n",
    "                leftb += 1\n",
    "            res = min(res, leftb + righta)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        # 枚举分割线\n",
    "        # 分割线左侧都是 a 右侧都是 b\n",
    "        n = len(s)\n",
    "        res = s.count('a')\n",
    "        ans = res\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                res -= 1\n",
    "            else:\n",
    "                res += 1\n",
    "            ans = min(ans, res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        # wocao前后缀这么玩是吧，好好好\n",
    "        # 最终结果是aaabbb这样的内容，那就一定存在一条线分割这个数组为前缀和后缀。\n",
    "        # 后缀中的a的数量应该删掉，前缀中b的数量应该删掉\n",
    "        n = len(s)\n",
    "        cnt = Counter(s)\n",
    "        ans = delete = cnt['a']\n",
    "        for i in range(n):\n",
    "            if s[i] == 'a':\n",
    "                delete -= 1\n",
    "            else:\n",
    "                delete += 1\n",
    "            if delete < ans:\n",
    "                ans = delete\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumDeletions(self, s: str) -> int:\n",
    "#         stk = []\n",
    "#         cnt = 0\n",
    "#         for c in s:\n",
    "#             if c == 'a':\n",
    "#                 if stk and stk[-1] == 'b':\n",
    "#                     stk.pop()\n",
    "#                     cnt += 1\n",
    "#                 else:\n",
    "#                     stk.append(c)\n",
    "#             else:\n",
    "#                 stk.append(c)\n",
    "#         return cnt\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        b, f = 0, 0\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                f = min(f + 1, b)\n",
    "            else:\n",
    "                b += 1\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        a, b = s.count('a'), s.count('b')\n",
    "        if not a or not b:\n",
    "            return 0\n",
    "        ans = min(a, b)\n",
    "        cnt = 0\n",
    "        for ch in s:\n",
    "            if ch == 'a':\n",
    "                a -= 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "            ans = min(ans, cnt + a)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        d=s.count('a')\n",
    "        ans=d\n",
    "        for c in s:\n",
    "            d+=1 if c=='b' else -1\n",
    "            if d<ans:\n",
    "                ans=d \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        leftb, righta = 0, s.count('a')\n",
    "        res = righta\n",
    "        for c in s :\n",
    "            if c == 'a':\n",
    "                righta -= 1\n",
    "            else:\n",
    "                leftb += 1\n",
    "            res = min(res, righta + leftb)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        ans = delete = s.count('a')\n",
    "        for i in s:\n",
    "            if i == 'a':\n",
    "                delete -= 1\n",
    "            else:\n",
    "                delete += 1\n",
    "            if delete < ans:\n",
    "                ans = delete\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        a_num = 0\n",
    "        b_num = 0\n",
    "        for ch in s:\n",
    "            if ch=='a':\n",
    "                a_num += 1\n",
    "                if b_num > 0:\n",
    "                    ans = min(ans + 1, b_num)\n",
    "            else:\n",
    "                b_num += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        frontb = 0\n",
    "        backa = s.count('a')\n",
    "        ans = frontb + backa\n",
    "        for i in range(len(s)+1):\n",
    "            ans = min(ans,frontb+backa)\n",
    "            if i<(len(s)):\n",
    "                if s[i]=='a':\n",
    "                    backa -= 1\n",
    "                else:\n",
    "                    frontb += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        \"\"\"将问题转化为求【最长平衡子序列问题】\"\"\"\n",
    "        n = len(s)\n",
    "\n",
    "        # dp[0]: 以 a 结尾的最长平衡子序列长度\n",
    "        # dp[1]: 以 b 结尾的最长平衡子序列长度\n",
    "        dp = [1, 0] if s[0] == 'a' else [0, 1]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if s[i] == 'a':\n",
    "                # a 前面只能是 a\n",
    "                dp[0] += 1\n",
    "            else:\n",
    "                # b 前面既可以是 a 又可以是 b\n",
    "                dp[1] = max(dp) + 1\n",
    "\n",
    "        return n - max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        end_with_a=0\n",
    "        end_with_b=0\n",
    "\n",
    "        for c in s:\n",
    "            if(c=='a'):\n",
    "                end_with_a+=1\n",
    "                \n",
    "            else:\n",
    "                end_with_b=max(end_with_a,end_with_b)+1\n",
    "\n",
    "        return len(s)-max(end_with_a,end_with_b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        a = s.count(\"a\")\n",
    "        b = s.count(\"b\")\n",
    "\n",
    "        pre_a = pre_b = 0\n",
    "        ans = pre_b + a - pre_a\n",
    "        for w in s:\n",
    "            if w == \"a\":\n",
    "                pre_a += 1\n",
    "            else:\n",
    "                pre_b += 1\n",
    "            cur = pre_b + a - pre_a\n",
    "            if cur < ans:\n",
    "                ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        leftb, righta = 0, s.count(\"a\")\n",
    "        cnt = righta\n",
    "        for ch in s:\n",
    "            if ch == \"a\":\n",
    "                righta -= 1\n",
    "            else:\n",
    "                leftb += 1\n",
    "            cnt = min(cnt, leftb + righta)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        stk = []\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                if stk and stk[-1] == 'b':\n",
    "                    stk.pop()\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    stk.append(c)\n",
    "            else:\n",
    "                stk.append(c)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        leftb, righta = 0, s.count('a')\n",
    "        res = righta\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                righta -= 1\n",
    "            else:\n",
    "                leftb += 1\n",
    "            res = min(res, leftb + righta)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        stk = []\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                if stk and stk[-1] == 'b':\n",
    "                    stk.pop()\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    stk.append('a')\n",
    "            else:\n",
    "                stk.append('b')\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for idx,c in enumerate(s):\n",
    "            if c == 'b':\n",
    "                stack.append(c)\n",
    "            elif stack:\n",
    "                stack.pop()\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        leftb, righta = 0, s.count('a')\n",
    "        res = righta\n",
    "        for c in s:\n",
    "            if c == 'a':\n",
    "                righta -= 1\n",
    "            else:\n",
    "                leftb += 1\n",
    "            res = min(res, leftb + righta)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        if 'ba' not in s:\n",
    "            return 0\n",
    "\n",
    "        n = len(s)\n",
    "        a_num = s.count('a')\n",
    "        a_list = []\n",
    "        b_list = []\n",
    "        count_a, count_b = 0, 0\n",
    "        for i in range(n):\n",
    "            if s[i] == 'a':\n",
    "                count_a += 1\n",
    "            else:\n",
    "                count_b += 1\n",
    "                if i + 1 < n and s[i + 1] == 'a':\n",
    "                    a_list.append(a_num - count_a)\n",
    "                    b_list.append(count_b)\n",
    "        answer = min(a_list[0], b_list[-1])\n",
    "        for i in range(len(b_list) - 1):\n",
    "            if (temp := b_list[i] + a_list[i + 1]) < answer:\n",
    "                answer = temp\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        dp=[0 for _ in range(len(s)+1)]\n",
    "        cntB=0\n",
    "        for i, c in enumerate(s):\n",
    "            if c=='b':\n",
    "                cntB+=1\n",
    "                dp[i+1]=dp[i]\n",
    "            else:\n",
    "                dp[i+1]=min(dp[i]+1, cntB)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        dp = [0 for i in range(len(s))]\n",
    "        cnt_b = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'a':\n",
    "                dp[i] = min(dp[i - 1] + 1, cnt_b)\n",
    "            elif s[i] == 'b':\n",
    "                dp[i] = dp[i - 1]\n",
    "                cnt_b += 1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cntb = 0\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            if s[i-1] == 'b':\n",
    "                dp[i] = dp[i-1]\n",
    "                cntb += 1\n",
    "            else:\n",
    "                dp[i] = min(dp[i-1]+1,cntb)\n",
    "        return dp[-1]\n",
    "\n",
    "        # for c in s:\n",
    "        #     if c == 'b':\n",
    "        #         leftb += 1\n",
    "        #     else:\n",
    "        #         righta -= 1\n",
    "        #     # 枚举所有分割线\n",
    "        #     res = min(res,leftb+righta)\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        dp = [0]*len(s)\n",
    "        cntb = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'b':\n",
    "                cntb += 1\n",
    "                dp[i] = dp[i-1]\n",
    "            else:\n",
    "                dp[i] = min(dp[i-1]+1, cntb)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        prefix = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            prefix[i] = prefix[i-1] + 1 if s[i-1] == \"a\" else prefix[i-1]\n",
    "        \n",
    "        post = 0\n",
    "        maxLen = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            maxLen = max(maxLen, post + prefix[i+1])\n",
    "            if s[i] == \"b\": post += 1\n",
    "        return len(s) - max(maxLen, post)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        prefix = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            prefix[i] = prefix[i-1] + 1 if s[i-1] == \"a\" else prefix[i-1]\n",
    "        \n",
    "        post = 0\n",
    "        maxLen = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            maxLen = max(maxLen, post + prefix[i+1])\n",
    "            if s[i] == \"b\": post += 1\n",
    "        return len(s) - max(maxLen, post)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        prefix = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            prefix[i] = prefix[i-1] + 1 if s[i-1] == \"a\" else prefix[i-1]\n",
    "        \n",
    "        post = 0\n",
    "        maxLen = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            maxLen = max(maxLen, post + prefix[i+1])\n",
    "            if s[i] == \"b\": post += 1\n",
    "        return len(s) - max(maxLen, post)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cntb = 0\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            if s[i-1] == 'b':\n",
    "                dp[i] = dp[i-1]\n",
    "                cntb += 1\n",
    "            else:\n",
    "                dp[i] = min(dp[i-1]+1,cntb)\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "        # for c in s:\n",
    "        #     if c == 'b':\n",
    "        #         leftb += 1\n",
    "        #     else:\n",
    "        #         righta -= 1\n",
    "        #     # 枚举所有分割线\n",
    "        #     res = min(res,leftb+righta)\n",
    "        # return res\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for i,x in enumerate(s):\n",
    "            if x == 'a':\n",
    "                ans += i-cnt\n",
    "                cnt += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        dp = [1] * len(s)\n",
    "        a_idx, b_idx = -1, -1\n",
    "        max_rise = 0\n",
    "        for idx, c in enumerate(s):\n",
    "            if c == 'a':\n",
    "                if a_idx >= 0:\n",
    "                    dp[idx] = dp[a_idx] + 1\n",
    "                a_idx = idx\n",
    "            else:\n",
    "                if a_idx >= 0:\n",
    "                    dp[idx] = max(dp[idx], dp[a_idx] + 1)\n",
    "                if b_idx >= 0:\n",
    "                    dp[idx] = max(dp[idx], dp[b_idx] + 1)\n",
    "                b_idx = idx\n",
    "            max_rise = max(max_rise, dp[idx])\n",
    "        return len(s) - max_rise"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dpa, dpb = [0] * n, [0] * n\n",
    "        if s[0] == 'a':\n",
    "            dpa[0] = 1\n",
    "            dpb[0] = 0\n",
    "        else:\n",
    "            dpa[0] = 0\n",
    "            dpb[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if s[i] == 'a':\n",
    "                dpa[i] = dpa[i - 1] + 1\n",
    "                dpb[i] = dpb[i - 1]\n",
    "            else:\n",
    "                dpa[i] = dpa[i - 1]\n",
    "                dpb[i] = max(dpa[i - 1], dpb[i - 1]) + 1\n",
    "        return n - max(max(dpa), max(dpb))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if len(Counter(s)) == 1:\n",
    "            return 0\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        res = inf\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == 'b':\n",
    "                cnt += 1\n",
    "\n",
    "            left[i] = cnt\n",
    "        cnt = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            right[i] = cnt\n",
    "            if s[i] == 'a':\n",
    "                cnt += 1\n",
    "     \n",
    "        for i in range(n):\n",
    "            tmp = left[i] + right[i]\n",
    "            res = min(res, tmp)\n",
    "        res = min(res, min(left[-1], right[0]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = [0]*n\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if(s[i] == 'b'):\n",
    "                cnt += 1\n",
    "            left[i] = cnt \n",
    "        right = [0]*n\n",
    "        cnt = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(s[i] == 'a'):\n",
    "                cnt += 1\n",
    "            right[i] = cnt \n",
    "        result = min(right[0],left[n-1])\n",
    "        for i in range(n-1):\n",
    "            result = min(result,left[i] + right[i+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = [0]*n\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if(s[i] == 'b'):\n",
    "                cnt += 1\n",
    "            left[i] = cnt \n",
    "        right = [0]*n\n",
    "        cnt = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(s[i] == 'a'):\n",
    "                cnt += 1\n",
    "            right[i] = cnt \n",
    "        result = min(right[0],left[n-1])\n",
    "        for i in range(n-1):\n",
    "            result = min(result,left[i] + right[i+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = [0]*n\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if(s[i] == 'b'):\n",
    "                cnt += 1\n",
    "            left[i] = cnt \n",
    "        right = [0]*n\n",
    "        cnt = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(s[i] == 'a'):\n",
    "                cnt += 1\n",
    "            right[i] = cnt \n",
    "        result = min(right[0],left[n-1])\n",
    "        for i in range(n-1):\n",
    "            result = min(result,left[i] + right[i+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        a_num = [0] * (n+1)\n",
    "        b_num = [0] * (n+1)\n",
    "\n",
    "        a_num[0] = s.count('a')\n",
    "\n",
    "        res = math.inf\n",
    "        for i in range(n):\n",
    "            if (s[i] == 'b'):\n",
    "                b_num[i+1] = b_num[i]+1\n",
    "            else:\n",
    "                b_num[i+1] = b_num[i]\n",
    "            \n",
    "            if (s[i] == 'a'):\n",
    "                a_num[i+1] = a_num[i]-1\n",
    "            else:\n",
    "                a_num[i+1] = a_num[i]\n",
    "            res = min(res,a_num[i]+b_num[i])\n",
    "        #print(a_num)\n",
    "        #print(b_num)\n",
    "        return min(res,a_num[n]+b_num[n])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l,r = [0] * n, [0] * n\n",
    "        for i in range(1, n):\n",
    "            l[i] = l[i-1]\n",
    "            if s[i-1] == 'b':\n",
    "                l[i] += 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            r[i] = r[i+1]\n",
    "            if s[i+1] == 'a':\n",
    "                r[i] += 1\n",
    "        ret = min(r[0],l[-1])\n",
    "        for i in range(1,n-1):\n",
    "            ret = min(ret, l[i] + r[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        dp = [0 for _ in range(len(s)+1)]\n",
    "        cnt = [0 for _ in range(len(s)+1)]\n",
    "        count=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='b':\n",
    "                count+=1\n",
    "            cnt[i+1]=count\n",
    "        for i in range(1,len(s)+1):\n",
    "            if s[i-1]=='b':\n",
    "                dp[i]=dp[i-1]\n",
    "            else:\n",
    "                dp[i]=min(dp[i-1]+1, cnt[i])\n",
    "        # return cnt\n",
    "        return dp[len(s)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        preb = [0] * (len(s) + 1)\n",
    "        sufa = [0] * (len(s) + 1)\n",
    "        for i in range(len(s)):\n",
    "            preb[i + 1] += 1 + preb[i] if s[i] == 'b' else preb[i]\n",
    "            sufa[len(s) - 1 - i] = 1 + sufa[len(s) - i] if s[len(s) - 1 - i] == 'a' else sufa[len(s) - i]\n",
    "        ans = inf\n",
    "        for i in range(len(s) + 1):\n",
    "            ans = min(ans, preb[i] + sufa[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        if len(s) == 1:\n",
    "            return 0\n",
    "        a_list = []\n",
    "        b_list = []\n",
    "        for i in range(len(s)):\n",
    "            if i == 0:\n",
    "                if s[i] == \"a\":\n",
    "                    a_list.append(1)\n",
    "                    b_list.append(0)\n",
    "                else:\n",
    "                    a_list.append(0)\n",
    "                    b_list.append(1)\n",
    "            else:\n",
    "                if s[i] == \"a\":\n",
    "                    a_list.append(a_list[-1] + 1)\n",
    "                    b_list.append(b_list[-1])\n",
    "                else:\n",
    "                    a_list.append(a_list[-1])\n",
    "                    b_list.append(b_list[-1] + 1)\n",
    "        res = min(a_list[-1], b_list[-1])\n",
    "        for i in range(len(s)):\n",
    "            left_delete_num = b_list[i]\n",
    "            right_delete_num = a_list[-1] - a_list[i]\n",
    "            if (left_delete_num + right_delete_num) < res:\n",
    "                res = left_delete_num + right_delete_num\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n, res = len(s), inf\n",
    "        pre_b, suf_a = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i in range(1, n+1):\n",
    "            pre_b[i] = pre_b[i - 1] + (1 if s[i - 1] == 'b' else 0)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suf_a[i] = suf_a[i + 1] + (1 if s[i] == 'a' else 0)\n",
    "        # print(pre_b, suf_a)\n",
    "        for j in range(n + 1):\n",
    "            # print(res)\n",
    "            res = min(res, pre_b[j] + suf_a[j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n, res = len(s), inf\n",
    "        pre_b, suf_a = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i in range(1, n+1):\n",
    "            pre_b[i] = pre_b[i - 1] + (1 if s[i - 1] == 'b' else 0)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suf_a[i] = suf_a[i + 1] + (1 if s[i] == 'a' else 0)\n",
    "        for j in range(n + 1):\n",
    "            res = min(res, pre_b[j] + suf_a[j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = [0]*n\n",
    "        suf = [0]*n\n",
    "        dict1 = {'a':0,'b':1}\n",
    "        dict2 = {'a':1,'b':0}\n",
    "        for i in range(1,n):\n",
    "            pre[i] = pre[i-1]+dict1[s[i-1]]\n",
    "        \n",
    "        for i in range(n-2,-1,-1):\n",
    "            suf[i] = suf[i+1]+dict2[s[i+1]]\n",
    "\n",
    "        res = inf\n",
    "        for i in range(n):\n",
    "            if suf[i]+pre[i]<res:\n",
    "                res = suf[i]+pre[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n, res = len(s), inf\n",
    "        pre_b, suf_a = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i in range(1, n+1):\n",
    "            pre_b[i] = pre_b[i - 1] + (1 if s[i - 1] == 'b' else 0)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suf_a[i] = suf_a[i + 1] + (1 if s[i] == 'a' else 0)\n",
    "        for j in range(n + 1):\n",
    "            res = min(res, pre_b[j] + suf_a[j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        preSum, sufSum = [0] * (n + 7), [0] * (n + 7)\n",
    "        for i in range(n):\n",
    "            preSum[i + 1] = preSum[i] + int(s[i] == 'b')\n",
    "            sufSum[n - i] = sufSum[n - i + 1] + int(s[n - i - 1] == 'a')\n",
    "        ret = n\n",
    "        for i in range(n+1):\n",
    "            ret = min(ret, preSum[i] + sufSum[i + 1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        left_b = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            if s[i] == \"b\":\n",
    "                left_b[i+1] = left_b[i] + 1\n",
    "            else:\n",
    "                left_b[i+1] = left_b[i]\n",
    "        \n",
    "        right_a = [0] * (n + 1)\n",
    "        for j in range(n-1, -1, -1):\n",
    "            if s[j] == \"a\":\n",
    "                right_a[j] = right_a[j+1] + 1\n",
    "            else:\n",
    "                right_a[j] = right_a[j+1]\n",
    "        \n",
    "        return min([left_b[i] + right_a[i] for i in range(n+1)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*2 for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == \"a\":\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = dp[i-1][1]+1\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0]+1\n",
    "                dp[i][1] = min(dp[i-1][1], dp[i-1][0])\n",
    "\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, s: str) -> int:\n",
    "        \"\"\"将问题转化为求【最长平衡子序列问题】\"\"\"\n",
    "        n = len(s)\n",
    "\n",
    "        # dp[i][0]: 以 s[i] == a 结尾的最长平衡子序列长度\n",
    "        # dp[i][1]: 以 s[i] == b 结尾的最长平衡子序列长度\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "        if s[0] == 'a':\n",
    "            dp[0][0] = 1\n",
    "        else:\n",
    "            dp[0][1] = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if s[i] == 'a':\n",
    "                # a 前面只能是 a\n",
    "                dp[i][0] = dp[i - 1][0] + 1\n",
    "                dp[i][1] = dp[i - 1][1]\n",
    "            else:\n",
    "                # b 前面既可以是 a 又可以是 b\n",
    "                dp[i][1] = max(dp[i - 1]) + 1\n",
    "                dp[i][0] = dp[i - 1][0]\n",
    "\n",
    "        return n - max(dp[-1])\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
